package com.lw.leetcode.dp.b;

/**
 * 221. 最大正方形
 *
 * @Author liw
 * @Date 2021/4/30 15:13
 * @Version 1.0
 */
public class MaximalSquare {

    public static void main(String[] args) {
        MaximalSquare test = new MaximalSquare();
        char[][] matrix = {{'0'}};
        int i = test.maximalSquare(matrix);

    }

    public int maximalSquare(char[][] matrix) {
        int x = matrix.length;
        int y = matrix[0].length;

        int[][] arr = new int[x + 1][y + 1];
        int max = 0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (matrix[i][j] == '1') {
                    arr[i + 1][j + 1] = Math.min(arr[i][j + 1], Math.min(arr[i + 1][j], arr[i][j])) + 1;
                    max = Math.max(max, arr[i + 1][j + 1]);
                }
            }
        }
        return max * max;
    }

}
